JOI 07春合宿 anagram(難易度6)
この問題では順列の考え方を用いる(数Aの典型問題である).
例えば, 文字列"HEART"を考える.
これがアナグラムの中で何番目かというのは次のように求められる.
"A...."の形の文字列は$ 4! = 24通り.
"E...."の形の文字列は$ 4! = 24通り.
"HA..."の形の文字列は$ 3! = 6通り
よって, "HEART"は$ 24 + 24 + 6 + 1 = 55番目の文字列である.
次に, 文字列"HEREH"を考える.
"E...."の形の文字列は$ 4!/(2! \cdot 1! \cdot 1!) = 12通り.
"HEE.."の形の文字列は$ 2!/(1! \cdot 1!) = 2通り.
"HEH.."の形の文字列は$ 2!/(1! \cdot 1!) = 2通り.
よって, "HEREH"は$ 12 + 2 + 2 + 1 = 17番目の文字列である.
このように, 同じものを含む順列を適用することによっていくつかの例を解くことができる. これを一般化してこの問題を解く.
まず, あらかじめ$ 0から$ 20までの階乗を前計算しておく.
文字列を受け取り, 各文字の出現回数を計算しておく.
そしてコードのように操作を行う(kaiは階乗の配列, cntは各文字の出現回数の配列)
https://gyazo.com/dca61adccd5c29f74c85983129c3c4c3
考察がかなり数学的であるが, まあ慣れればそんなに難しくはないかなという感じ(ただ, 難易度5とかと比べて実装も長く, どうやって実装するか考えることが多い).